# -*- coding: utf-8 -*-
# @Time     : 2021/11/27 9:07
# @Author   : wljess
# @File     : 插入排序.py
# @Describe : 
# @Software : PyCharm


def insert_sort(li):

    '''
    插入排序
    :param li: 待排序的列表
    :return:
    '''

    for i in range(1, len(li)):  # i代表摸到无序区牌的下标
        tmp = li[i]  # 每次从无序区摸到的牌存到临时变量中
        j = i - 1  # 代表手里的牌
        # 当手中的牌比摸到的牌大，手里牌向右移动，为防止索引越界，所以j >= 0
        while j >= 0 and li[j] > tmp:  # 找到插入摸到牌的位置
            # 手里牌向右移动，即将j位置的牌放赋值给j + 1的位置
            li[j + 1] = li[j]
            # j -= 1(继续比较j前一个位置与摸到牌的大小)
            j -= 1

        # 循环完之后将摸到的牌放到待插入的位置
        li[j + 1] = tmp
        print(f"第{i}躺排序：{li}")

    return li


if __name__ == '__main__':
    lst = [92, 18, 45, 36, 9, 8, 7, 19, 9, 20, 35]
    print(insert_sort(lst))
